package edu.ustb.mis.dm.util;

import java.util.ArrayList;
import java.util.List;

/**
 * 计算并输出组合数
 * 
 * @author Saya
 */
public class CombinationUtils {
	public static long getCnm(final int n, int m) {
		if ( (n < 0) || (m < 0)) {
			throw new IllegalArgumentException("n and m must be >= 0");
		}
		if ( (n == 0) || (m == 0)) {
			return 1;
		}
		if (m > n) {
			return 0;
		}
		if (m > n / 2.0) {
			m = n - m;
		}
		double result = 0.0;
		for (int i = n; i >= (n - m + 1); i--) {
			result += Math.log(i);
		}
		for (int i = m; i >= 1; i--) {
			result -= Math.log(i);
		}
		result = Math.exp(result);
		return Math.round(result);
	}

	public static <T>List<T> getValue(final List<T> source, int m, int x) {
		// 数组大小
		int n = source.size();
		// 存储组合数
		final List<T> result = new ArrayList<T>();
		int start = 0;
		while (m > 0) {
			if (m == 1) {
				// m == 1 时为组合数的最后一个字符
				result.add(source.get(start + x));
				break;
			}
			for (int i = 0; i <= n - m; i++) {
				final int cnm = (int)getCnm(n - 1 - i, m - 1);
				if (x <= cnm - 1) {
					result.add(source.get(start + i));
					// 启始下标前移
					start = start + (i + 1);
					// 搜索区域减小
					n = n - (i + 1);
					// 组合数的剩余字符个数减少
					m--;
					break;
				} else {
					x = x - cnm;
				}
			}
		}
		return result;
	}

	public static List<Integer> initData(final Long limit) {
		if (limit <= 0) {
			throw new IllegalArgumentException("limit must be > 0");
		} else {
			final List<Integer> source = new ArrayList<Integer>();
			for (int i = 0; i < limit; i++) {
				source.add(i);
			}
			return source;
		}
	}
}
